`
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
`

/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (max_k, prices) {
  const n = prices.length
  if (n <= 0) return 0

  // 一次交易由买入和卖出构成，至少需要两天。
  // 所以说有效的限制 k 应该不超过 n / 2，如果超过，就没有约束作用了，相当于 k 没有限制的情况
  if (max_k > n >> 1) {
    return maxProfit_inf(prices)
  }

  const dp = Array(n).fill(null).map(() => Array(max_k + 1).fill(null).map(() => [0, 0]));

  // k = 0 时的 base case
  // dp[-1][...][0] = dp[...][0][0] = 0
  // dp[-1][...][1] = dp[...][0][1] = -infinity
  for (let i = 0; i < n; i++) {
    dp[i][0][1] = -Infinity
    dp[i][0][0] = 0;
  }

  for (let i = 0; i < n; i++) {
    for (let k = max_k; k >= 1; k--) {
      // 处理边界
      if (i - 1 === -1) {
        dp[i][k][0] = 0
        dp[i][k][1] = -prices[i]
        continue
      }
      // 休息或卖出
      dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
      // 休息或买入
      dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
    }
  }

  return dp[n - 1][max_k][0]
};

// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
var maxProfit_inf = function (prices) {
  const n = prices.length

  let dp_0 = 0, dp_1 = -Infinity

  for (let i = 0; i < n; i++) {
    const tmp = dp_0
    // 休息或卖掉
    dp_0 = Math.max(dp_0, dp_1 + prices[i])
    // 休息或买入
    dp_1 = Math.max(dp_1, tmp - prices[i])
  }

  return dp_0
};